package com.longge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-06 02:17
 */
public class PermutationMul {

    ArrayList<List<Character>> res = new ArrayList<>();

    public String[] permutation(String S) {
        ArrayList<Character> path = new ArrayList<>();
        char[] chars = S.toCharArray();
        boolean[] visited = new boolean[chars.length];
        Arrays.sort(chars);
        backtrack(chars, path, visited);
        return res.stream().map(cs -> {
            StringBuilder sb = new StringBuilder();
            cs.forEach(sb::append);
            return sb.toString();
        }).collect(Collectors.toList()).toArray(new String[]{});
    }

    private void backtrack(char[] chars, ArrayList<Character> path, boolean[] visited) {
        if (path.size() == chars.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (visited[i] || (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1])) continue;
            path.add(chars[i]);
            visited[i]=true;
            backtrack(chars, path, visited);
            path.remove(path.size() - 1);
            visited[i]=false;
        }


    }
}
